iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0

題目簡述:
一個由小到大排列的整數陣列,寫一個函式回傳每個元素的平方,並且也是由小到大排列

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

直覺聯想暴力解:
把每個數平方後,再把結果sort,而這個方法也適用一開始給的array沒有sort過

時間複雜度:O(nlogn)
空間複雜度:O(n)

function sortedSquaredArray(array) {
  //建一個和array一樣大小的Array並全部填入0
  const sortedSquares = new Array(array.length).fill(0);
  for (let i = 0; i < array.length; i++) {
    const value = array[i];
    //把原本的array元素依序平放後放到創建的sortedSquares
    sortedSquares[i] = value * value;
  }
  return sortedSquares.sort((a, b) => a - b);
}

當然暴力後一定要嘗試優化!
想想看如何達到O(n)的時間?
但這個方法成立的前提是一開始array已經是由小到大排列好的
那我們應該要怎麼做?

以Array = [-7,-5,-3,2,3,8,11]為例
我們都知道,越小的負數平方會變成越大的數,且一開始最小的負數會在最左邊,最大的數會在最右邊

如此,我們可以拿陣列最右邊的元素去和最左邊的數,兩者以絕對值做比較,誰的平方大誰就擺在最右邊
相信經過前兩天利用指標的方式解題,心裡一定有些想法了!!?

沒錯,就是給建立一個start pointer 和 end pointer分別指向陣列的頭尾

一樣我們先宣告一個一樣大小且塞滿0的陣列:[0,0,0,0,0,0,0]

  1. | -7 | < | 11 | → [0,0,0,0,0,0,121]
  2. | -7 | < | 8 | → [0,0,0,0,0,64,121]
  3. | -7 | > | 3 | → [0,0,0,0,49,64,121]

以此類推...

這個方法就可以在O(n)的時間內解決,而且我們只需要檢查一次,空間複雜度一樣要 O(n)來建立結果


var sortedSquares = function(nums) {
  const sortedSquares = new Array(nums.length).fill(0);
  let start = 0;
  let end = nums.length - 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    const smallerVal = nums[start];
    const biggerVal = nums[end];
    if (Math.abs(smallerVal) > Math.abs(biggerVal)) {
      sortedSquares[i] = smallerVal * smallerVal;
      start++;
    } else {
      sortedSquares[i] = biggerVal * biggerVal;
      end--;
    }
  }
  return sortedSquares;
};

明日預告:找出最綿延的山 Longest Mountain in Array


上一篇
Day 06:3 Sum
下一篇
Day 08 : Longest Mountain in Array
系列文
30天用JavaScript刷題刷起來!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言